#include "stdio.h"
#include "stdlib.h"
#include "BPlusTree.h"

BPlusTreeNode *create_node(int is_leaf)
{
    BPlusTreeNode *node = malloc(sizeof(BPlusTreeNode));
    node->is_leaf = is_leaf;
    node->key_count = 0;
    for (int i = 0; i < M; i++)
    {
        node->keys[i] = 0;
        if (is_leaf)
        {
            node->data_ptr[i] = NULL;
        }
        else
        {
            node->children_ptr[i] = NULL;
        }
    }
    if (is_leaf)
    {
        node->prev_ptr = NULL;
        node->next_ptr = NULL;
    }
    else
    {
        node->children_ptr[M] = NULL;
    }
    return node;
}

BPlusTreeNode *find_node(BPlusTreeNode *root, int key)
{
    if (!root)
    {
        return NULL;
    }
    BPlusTreeNode *temp = root;
    for (int i = 0; !temp->is_leaf; i++)
    {
        int j = 0;
        while (j < temp->key_count && key >= temp->keys[j])
        {
            j++;
        }
        temp = temp->children_ptr[j];
    }
    return temp;
}

BPlusTree *create_tree()
{
    BPlusTree *tree = malloc(sizeof(BPlusTree));
    tree->root = NULL;
    tree->first_leaf = NULL;
    return tree;
}

BPlusTreeNode *insert_node(BPlusTree *tree, int key, void *data)
{
    if (!tree->root)
    {
        BPlusTreeNode *leaf = create_tree(0);
        leaf->keys[0] = key;
        leaf->data_ptr[0] = data;
        leaf->key_count = 1;
        tree->root = leaf;
        tree->first_leaf = leaf;
        return leaf;
    }
    BPlusTreeNode *leaf = find_node(tree, key);
    if (leaf->key_count < MAX_KEYS)
    {
        insert_leaf(leaf, key, data);
    }
    else
    {
        // 分裂树
    }
}
